package test1;

import java.util.Arrays;

public class Test4 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 5, 2, 5, 2, 5, 3, 4, 8, 9};
        int[] arr = count_sort(nums, getMax(nums));
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    private static int getMax(int[] nums) {
        int max = nums[0];
        for (int val : nums) {
            if (max < val) {
                max = val;
            }
        }
        return max;
    }

    private static int[] count_sort(int[] nums, int max) {
        int[] arr = Arrays.copyOf(nums, nums.length);
        int[] bucket = new int[max + 1];

        for (int val : arr) {
            bucket[val]++;
        }

        int sortedIndex = 0;
        for (int i = 0; i < bucket.length; i++) {
            while (bucket[i] > 0) {
                arr[sortedIndex++] = i;
                bucket[i]--;
            }
        }
        return arr;
    }
}
